package com.ljx.offer;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 李捷禧
 * Date: 2023/3/30
 * ClassName: C_56_1
 */

public class C_59_1 {
    /**
     * 优化完
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length +1 -k];
        for (int i = 0,j = 1 - k; i < nums.length; i++,j++) {
            if( j > 0 && deque.peekFirst() == nums[j - 1]){
                deque.removeFirst();
            }
            while (!deque.isEmpty() && nums[i] > deque.peekLast()){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            if(j >= 0) res[j] = deque.peekFirst();
        }
            return res;
    }

    /**
     * 难度：困难
     * 结果是对的，运行超时
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if(nums.length == 0) return new int[0];
        int[] arr = new int[nums.length + 1 -k];
        for (int i = 0; i < nums.length - k +1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i+k; j++) {
                max =Math.max(nums[j],max);
            }
            arr[i] = max;
        }
        return arr;
    }

    @Test
    public void test(){
        int[] arr = new int[]{1,3,-1,-3,5,3,6,7};
        int[] ints = maxSlidingWindow(arr, 3);
        for (int anInt : ints) {
            System.out.println(anInt);
        }

    }
}
